public class Solution200 {

    int[] dx=new int[]{1,0,-1,0};
    int[] dy=new int[]{0,1,0,-1};

    public int numIslands(char[][] grid) {
        int m=grid.length,n=grid[0].length;
        boolean[][] visit=new boolean[m][n];
        int ans=0;
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]=='1' && !visit[i][j]){
                  ans++;
                  dfs(i,j,visit,grid);
                }
            }
        }
        return ans;
    }

    private void dfs(int x, int y, boolean[][] visit, char[][] grid) {
        visit[x][y]=true;
        for (int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if (xx>=0 && xx<grid.length && yy>=0 && yy<grid[0].length
            && !visit[xx][yy] && grid[xx][yy]=='1'){
                dfs(xx,yy,visit,grid);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution200().numIslands(new char[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}}));
    }
}
